# source:https://leetcode.cn/problems/design-an-ordered-stream/ 设计
class OrderedStream:

    def __init__(self, n: int):
       self.store = ['']*n 
       self.ptr = 0
       self.length = n
    def insert(self, idKey: int, value: str) -> List[str]:
        self.store[idKey-1] = value
        ans = []
        while self.ptr < self.length and self.store[self.ptr]:
            ans.append(self.store[self.ptr])
            self.ptr += 1
        return ans


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

# source:https://leetcode.cn/problems/palindrome-partitioning-iii/ 划分型DP 记忆化搜索
from functools import cache
from math import inf
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)

        @cache
        def dfs(i, cnt):
            if cnt == 0:
                if i < 0:
                    return 0
                return inf
            if i < 0:
                return inf
            res = inf 
            for j in range(i+1):
                res = min(res, dfs(j-1, cnt-1)+f[j][i])
            return res

        f = [[0]*n for _ in range(n)]
        for length in range(n):
            for i in range(n - length):
                j = i + length
                if s[i] == s[j]:
                    if abs(i-j) <= 1:
                        f[i][j] = 0
                    else:
                        f[i][j] = f[i+1][j-1]
                else:
                    f[i][j] = f[i+1][j-1] + 1
        # print(f)
        return dfs(n-1, k)

# source: https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/ 状态机DP 记忆化搜索
from typing import List
from functools import cache

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        @cache
        def dfs(i):
            if i < 0:
                return 0, 0  # (最长正数长度, 最长负数长度)
            
            if nums[i] == 0:
                return 0, 0  # 0 不能用于乘积

            prev_pos, prev_neg = dfs(i-1)

            if nums[i] > 0:
                res1 = prev_pos + 1  # 继承正数序列
                res2 = prev_neg + 1 if prev_neg else 0  # 继承负数序列
            else:
                res1 = prev_neg + 1 if prev_neg else 0  # 负变正
                res2 = prev_pos + 1  # 正变负

            return res1, res2
        
        return max(dfs(i)[0] for i in range(len(nums)))  # 取所有索引的最大正数长度
